import java.util.ArrayList;


/**
 * This class demonstrates Huffman algorithm
 * @author Hyangjin Lee
 *
 */
public class HuffmanEncoder {
	
	private ArrayList<Node> array = new ArrayList<Node>();
	private ArrayList<Node> sorted = new ArrayList<Node>();
	private String code;
	private String input, output;

	/**
	 * 
	 * @param text
	 * @return
	 */
	public String encode(String text)
	{
		input = text;
		int counter = 0;
		Node root, last;
		int totalFreq = 0;
		
		//traverse the array to check if the letter already
		//exists.
		for(int i=0; i<text.length(); i++)
		{
			char temp = input.charAt(i);
//			int j=array.size();
			boolean flag = false; //shows if the letter has been settled
			
			if(array.isEmpty()) //if array is empty
			{
				array.add(new Node(temp, 1));
				flag = true;
				counter++;
			}
			else
			{
				//traverse to find temp
				for(int k=0; k<array.size(); k++)
				{
					Node curr = array.get(k);
					
					if(curr.getLetter()==temp)
					{
						curr.frequency++;
						flag = true;
					}
				}
				
				if(!flag)//if the letter wasn't in the array
				{
					array.add(new Node(temp, 1));
					flag = true;
					counter++;
				}
			}
		}//We're done with separating the letters and updating
		 //their frequencies.
		
		/**
		 * Check Point
		 */
		for(int i=0; i<array.size(); i++)
		{
			Node alala = array.get(i);
			System.out.println(alala.getLetter()+ "" + alala.frequency);
		}//Test Passed.
		
		//first we sum up the frequencies
		for(int i=0; i<array.size(); i++)
		{
			totalFreq+= array.get(i).frequency;
		}
		
		boolean flag = false;
		while(!flag)
		{
			//Now we need to get the smallest Node and remove it
			Node min = array.get(0);
			for(int i=1; i<array.size(); i++)
			{
				if(array.get(i).frequency <= min.frequency)
				{
					min = array.get(i);

				}
			}
			array.remove(array.indexOf(min));

			//We get the second smallest Node
			//in the case there are multiple candidates for the 
			//second smallest Node, the last one will be picked
			Node min2 = array.get(0);
			for(int j=0; j<array.size(); j++)
			{
				if(array.get(j).frequency <=  min2.frequency)
				{
					min2 = array.get(j);
				}
			}
			array.remove(array.indexOf(min2));

			//Now we make a pseudo Node combining the first and 
			//second smallest Nodes and add it back to the array.
			int freqs = min.frequency + min2.frequency;
			array.add(new Node(freqs, min, min2));
			min.setParent(array.get(array.size()-1));
			min2.setParent(array.get(array.size()-1));	
			
			if(array.size()==1)
			{
				flag = true;
				root = array.get(0);
				if(root.frequency != totalFreq)
					System.out.println("Frequency doesn't match!!");
			}//In the final step, root is instantiated and its frequency
			//should equal totalFreq. As we confirm it, we set it as the root.
		}
		
		//Time to encode!!
		//First we traverse all the way down to each leaves
		//And then encode!	
		int count = 0;
		array.get(0).setCode("");
		
		
		if(sorted.isEmpty())
		{
			sorted.add(array.get(0));
		}


		for(int i=0; i<sorted.size(); i++)
		{
			boolean flg = false;
			Node curr = sorted.get(i);
			if(curr.getLetter()==0)
			{
				curr.getLeft().setCode(curr.getCode()+"0");
				sorted.add(curr.getLeft());
				curr.getRight().setCode(curr.getCode()+"1");
				sorted.add(curr.getRight());
				sorted.remove(i);
				flg = true;
			}


			if(flg)
			{
				break;
			}
		}
		
		/**
		 * Check Point
		 */
		for(int i=0; i<sorted.size(); i++)
		{
			Node alala = sorted.get(i);
			System.out.println(alala.getLetter()+ "" + alala.getCode());
		}//Test Passed.
		System.out.println(input);
		System.out.println(text);
			
		//Time to encode the input sentence!
		for(int i=0; i<input.length(); i++)
		{
			char temp = input.charAt(i);
			
			for(int j=0; j<sorted.size(); j++)
			{
				Node curr = sorted.get(j);
				if(temp == curr.getLetter())
				{
					output += curr.getCode();
				}
			}
		}
			
		
		return output;
	}
	
	
	
	/**
	 * 
	 * @param filename
	 * @return
	 */
	public String encodeAdaptive(String filename)
	{
		
		
		return "";
	}
	
	
//	public String decode(String encodedText,  YourDataStructure decode table)
//	{
//		
//		return "";
//	}
}
